In order to perform decoding operation in a Viterbi decoder, paths of finite lengths each to serve as a candidate for a most probable path as a transmission path are called survivor paths and stored in a path memory with respect to states on a code trellis of interest.
A bit which is common to previous surviving paths of a length about 4 to 5 times a code constraint length, in which the above survivor paths are assumed to effectively converge into one path, is output as decoded data.
In this case, the survivor paths are stored as follows:
In consideration of a unit cell structure of a trellis diagram as shown in FIG. 2A, state transition information between adjacent times (i.e., 1-bit information representing that which is more probable that state X.sub.k+1 at a time (k+1) is reached from state X.sub.k or from state X.sub.k ' at a time immediately before time (k+1)) is stored in a corresponding memory circuit.
Such 1-bit state transition information is called trellis connection data and is stored, with respect to each state, for each decoding step.
Therefore, in order to execute decoding on the basis of surviving paths thus stored, it becomes necessary to trace backward on the basis of preceding state transition information from the most probable state at time k (in which the probability of the surviving path stored with respect to this state is larger than that of any surviving path stored with respect to any other state), and decoded data is determined in accordance with state X.sub.k-v (where v is a surviving path length) which is finally reached. That is, so-called "trace back" must be performed.
In this case, basically, if trace back from time k to time k-v is not completed during one decoding step, decoded data cannot be output. In order to explain this more clearly, assume that a surviving path memory circuit is realized by a random-access memory as shown in FIG. 3, and that an ordinate direction corresponds to a trellis state and an abscissa direction corresponds to a time axis. Especially, assume that a decoding operation at time k is completed and a decoding operation of time (k+1) is started.
State transition information determined by an operation unit on the basis of a Viterbi algorithm are sequentially written in a memory in the vertical direction. In this case, in order to perform decoding, trace back must be executed in the horizontal direction before writing is completed and must reach, for example, the left end of the memory shown in FIG. 3.
In this case, trace back means repetition of a cycle such as accessing of an address .fwdarw. reading of state transition information .fwdarw. determination of an address to be accessed (at an immediately preceding time). Therefore, normally, writing of state transition information in the memory and track back operation are alternately performed.
However, as is apparent from FIG. 3, if the number of trellis states is different from the surviving path length (e.g., if the memory of FIG. 3 is a rectangle elongated in the horizontal direction), trace back does not reach the left end, even when writing of state transition information is completed with respect to all the states at time (k+1).
Moreover, assume that the numbers of trellis states and the surviving path length are the same with each other, and that the circuit configuration of a decoder is such that state transition information with respect to a plurality of states can be obtained at the same time. In this case, if these state transition information are written in a memory at a time, when the writing operation is completed with respect to all the states, trace back can be executed by only a portion of the path length. That is, the surviving paths can be traced back to only an intermediate stage. As a result, conventionally, it is difficult to conveniently control the memory, unless proper matching is achieved between the number of trellis states and the survivor path length.
However, depending on an S/N ratio of input data supplied to a decoder, there often appears a demand to increase a surviving path length or a degree of freedom of a circuit configuration of an operation unit. Management of a path memory according to other decoding methods is exemplified in IEEE "TRANSACTION OF COMMUNICATIONS", VOL. COM 29, No. 9, SEPTEMBER 1981. However, no drastic improvement in techniques is described therein.